package com.Sep_Twenty;

import java.util.Arrays;

/**
 * 698. 划分为k个相等的子集
 * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 *https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
 *
 * 2022/09/20 12:46
 */

public class Solution698 {

    static int[] budget;

    public static boolean canPartitionKSubsets(int[] nums, int k) {
        if (k==1) return true;
        int sum=0;
        for (int i:nums){
            sum+=i;
        }
        if (sum%k!=0) return false;
        sum/=k;
        Arrays.sort(nums);
        budget=new int[k];
        Arrays.fill(budget,sum);
        return dfs(k,nums,nums.length-1);
    }

    public static boolean dfs(int k, int[] nums, int cur){
        if (cur<0) return true;
        for (int i=0;i<k;i++)
        {
            if(i > 0 && budget[i] ==budget[i - 1]) continue;
            if (budget[i]==nums[cur]||budget[i]-nums[cur]>=nums[0])
            {
                budget[i]-=nums[cur];
                if (dfs(k,nums,cur-1)) return true;
                budget[i]+=nums[cur];
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums={4, 3, 2, 3, 5, 2, 1};
        System.out.println(canPartitionKSubsets(nums,4));
    }

}
